package Dynamic_programming;

import org.junit.Test;

import java.math.BigDecimal;
import java.util.*;

/**
 * @Author 万家欣
 * @Date 2022/4/6 9:14
 * @Version 1.0
 */
public class test03 {
    int N = 20010, M = N * 2, idx = 0;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    int[] f1 = new int[N], f2 = new int[N], g = new int[N], p = new int[N];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    @Test
    public void pp(){
        String s ="COL4,COL16,COL17,COL18,COL19,COL20,COL21,COL22,COL23,COL24,COL25,COL26,COL27,COL28,COL29,COL30,COL31,COL32,COL33,COL34,COL35,COL36,COL37,COL38,COL39,COL40,COL41,COL42,COL43,COL44,COL45,COL46,COL47,COL48,COL49,COL50,COL51,COL52,COL53,COL54,COL55,COL56,COL57,COL58,COL336,COL60,COL61,COL337,COL63,COL64,COL65,COL66,COL67,COL68,COL69,COL70,COL71,COL72,COL73,COL74,COL75,COL76,COL77,COL338,COL79,COL80,COL81,COL82,COL341,COL84,COL85,COL86,COL87,COL335,COL89,COL90,COL91,COL92,COL93,COL94,COL95,COL96,COL97,COL98,COL99,COL100,COL101,COL102,COL103,COL104,COL105,COL106,COL107,COL108,COL109,COL110,COL111,COL112,COL113,COL114,COL115,COL116,COL117,COL118,COL119,COL120,COL121,COL122,COL123,COL124,COL125,COL126,COL127,COL128,COL129,COL340,COL131,COL132,COL133,COL319,COL339";
        String[] temp =s.split(",");
        System.out.println(temp.length);
    }
    public int countPrimeSetBits(int left, int right) {
        int[] temp = new int[right + 1];
        temp[1] = 1;temp[2] = 1;
        for (int i = 3; i < temp.length; i++) {
            if(i % 2 == 0){
                temp[i] = temp[i / 2];
            }else {
                temp[i] = temp[i - 1] + 1;
            }
        }
        Set<Integer> t = new HashSet<>();
        int sum = 0;
        for (int i = left; i <= right ; i++) {
            if(t.contains(temp[i])){
                sum ++;
            }
        }
        return sum;
    }
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        Arrays.fill(he, -1);
        //通过这个循环获取每一个数的映射，e数组为其子
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            add(a, b); add(b, a);
        }
        List<Integer> ans = new ArrayList<>();
        dfs1(0, -1);
        dfs2(0, -1);
        int min = n;
        for (int i = 0; i < n; i++) {
            int cur = Math.max(g[i], f1[i]);
            if (cur < min) {
                ans.clear();
                ans.add(i);
                min = cur;
            } else if (min == cur) {
                ans.add(i);
            }
        }
        return ans;
    }
    int dfs1(int u, int fa) {
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            int sub = dfs1(j, u) + 1;
            if (f1[u] < sub) {
                f2[u] = f1[u];
                f1[u] = sub;
                p[u] = j;
            } else if (f2[u] < sub) {
                f2[u] = sub;
            }
        }
        return f1[u];
    }
    void dfs2(int u, int fa) {
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            if (p[u] != j) g[j] = Math.max(g[j], f1[u] + 1);
            else g[j] = Math.max(g[j], f2[u] + 1);
            g[j] = Math.max(g[j], g[u] + 1);
            dfs2(j, u);
        }
    }
    public boolean rotateString(String s, String goal) {
        if(s.length() != goal.length()){
            return false;
        }
        return (s+s).contains(goal);
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        int l = 0;
        int r = matrix[0].length - 1;
        while (l >=0 && l < matrix.length && r >=0 && r < matrix[0].length){
            if(matrix[l][r] > target){
                r--;
            }
            if(matrix[l][r] < target){
                l ++;
            }
            if(matrix[l][r] == target){
               return true;
            }
        }
        return r >=0 && l <matrix.length && matrix[l][r] == target;
    }
    public int getKthMagicNumber(int k) {
        int[] temp = new int[k];
        int a=1,b=1,c=1;
        for (int i = 0; i < k; i++) {
            temp[i] = Math.min(a * 3,Math.max(b * 5,c * 7));
            if(temp[i] == 3 * a){
                a ++;
            }
            if(temp[i] == b * 5){
                b ++;
            }
            if(temp[i] == c * 7){
                c ++;
            }

        }
        return temp[k - 1];
    }
    public int singleNumber(int[] nums) {
            int res = 0;
        for (int i = 0; i < 32; i++) {

            int temp = 0;
            for (int j = 0; j < nums.length; j++) {
                temp += ((nums[j] << i) & 1);
            }
            if(temp % 3 != 0){
                res |= (1 << i);
            }
        }
        return res;

    }
    public int maximumWealth(int[][] accounts) {
        Optional<int[]> temp = Arrays.stream(accounts).max((a, b)->{
         int x=   Arrays.stream(a).sum();
         int y=   Arrays.stream(b).sum();
            return x-y;
        });
        return Arrays.stream(temp.get()).sum();
    }
    public int uniqueMorseRepresentations(String[] words) {
String[] temp = new String[]{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",
        ".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    Set<String> set = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < words[i].length(); j++) {
                stringBuilder.append(temp[words[i].charAt(i) - 'a']);
            }
            set.add(stringBuilder.toString());
        }
        return set.size();
    }
    public int[] numberOfLines(int[] widths, String s) {
        int index = 0;
        int temp = 0;
        for (int i = 0; i < s.length(); i++) {
            int x = widths[s.charAt(i) - 'a'];
            if(temp + x > 100){
                index ++;
                temp = 0;
                i--;
            }else if(temp + x == 100){
                index ++;
                temp = 0;
            }else {
                temp += x;
            }
        }
        return new int[]{index,temp};
    }
    public String customSortString(String order, String s) {
        int[] temp = new int[order.length()];
        int[] t = new int[26];
        for (int i = 0; i < s.length(); i++) {
            int index = order.indexOf(s.charAt(i));
            if(index != -1){
                temp[index]++;
            }else {
                t[s.charAt(i) - 'a']++;
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < temp.length; i++) {
            for (int j = 0; j < temp[i]; j++) {
                stringBuilder.append(order.charAt(i));
            }
        }
        for (int i = 0; i < t.length; i++) {
            for (int j = 0; j < t[i]; j++) {
                char c = (char) (i+'a');
                stringBuilder.append(c);
            }
        }
        return stringBuilder.toString();
    }
    public NestedInteger deserialize(String s) {
        if(s == null) return new  NestedInteger();
        if(s.charAt(0)!='[')  return new NestedInteger(Integer.parseInt(s));
        if(s.length()<=2) return new  NestedInteger();
        NestedInteger res = new NestedInteger();
        int start=1,cnt=0;
        for (int i=1;i<s.length();i++){
            if(cnt==0&&(s.charAt(i)==','||i==s.length()-1)){
                res.add(deserialize(s.substring(start,i-start)));
                start=i+1;
            }
            else if(s.charAt(i)=='[') {
                cnt++;
            } else if(s.charAt(i)==']') cnt--;
        }
        return res;
    }
}
